package 力扣;

import java.util.ArrayList;
import java.util.List;

/**
 *给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
 *
 * 返回 s 所有可能的分割方案。
 *
 * 示例:
 *
 * 输入: "aab"
 * 输出:
 * [
 *   ["aa","b"],
 *   ["a","a","b"]
 * ]
 */
public class _131分割回文串 {

    public List<List<String>> partition(String s) {
        List<List<String>> ret = new ArrayList<List<String>>();
        List<String> list = new ArrayList<String>();

        doPartition(list,s,ret);
        return ret;
    }


    public void doPartition(List<String>  list,String s, List<List<String>> ret){
        if( s.length() == 0){
            ret.add(new ArrayList<>(list));
            return;
        }

        for (int i = 0; i < s.length(); i++) {
            if( isPartition(s,0,i)){
                    list.add(s.substring(0,i+1));
                    doPartition(list,s.substring(i+1),ret);
                list.remove(list.size()-1); // 移一位就行了
            }
        }

    }
    public void doPartition2(List<String>  list,String s, List<List<String>> ret){
        if( s.length() == 0 ){
            ret.add(new ArrayList<>(list));
        }
        for (int i = 0; i < s.length() ; i++) {
            if(isPartition(s,0,i)){
                list.add(s.substring(0,i+1));
                doPartition2(list,s.substring(i+1),ret);
                list.remove(list.size()-1);
            }

        }


    }

    private boolean isPartition(String str, int start, int end) {
        while ( start< end ){
            if(str.charAt(start++) != str.charAt(end--)){
                return false;
            }
        }
        return true;
    }

}
